package class_0904BinarySearchTree;
public class BinarySearchTree {
    private Node root;

    public static class Node {
        int val;
        Node left;
        Node right;
        Node p;

        public Node(int val) {
            this.val = val;
        }
    }
    /**
     * @param cur 指定节点
     * @param val 查找值
     * @return 返回值所在节点的地址。
     */
    public static Node search(Node cur, int val) {
        if (cur == null || cur.val == val) {
            return cur;
        }
        if (cur.val < val) {
            return search(cur.right, val);
        } else {
            return search(cur.left, val);
        }
    }

    public Node search(int val) {
        Node cur = root;
        while (cur != null) {
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                // cur.val == val;
                return cur;
            }
        }
        //cur == null;
        return null;
    }

    public static Node maximum(Node head) {
        Node p = null;
        Node cur = head;
        while (cur != null) {
            p = cur;
            cur = cur.right;
        }
        return p;
    }

    public static Node minimum(Node head) {
        Node p = null;
        Node cur = head;
        while (cur != null) {
            p = cur;
            cur = cur.left;
        }
        return p;
    }

    public static Node predecessor(Node head) {
        if (head != null) {
            if (head.left != null) {
                // 如果有左子树，前驱节点是左子树中的最大节点
                return maximum(head.left);
            } else {
                // 如果没有左子树，向上查找前驱节点
                Node cur = head.p; // 追溯父节点
                while (cur != null && head == cur.left) {
                    head = cur;
                    cur = cur.p; // 继续向上查找祖先节点
                }
                return cur; // 最终返回前驱节点
            }
        }
        return null; // 如果head为空，返回null
    }

    public static Node successor(Node head) {
        if (head != null) {
            // 如果节点的右子树非空，那么右子树的最小节点就是它的后继
            if (head.right != null) {
                return minimum(head.right);
            } else {
                // head.right == null
                // 那么head节点的后继节点是某个最近底层祖先节点的右子树
                Node cur = head.p;  // 追溯父节点
                while (cur != null && head == cur.right) {
                    head = cur;
                    cur = cur.p;  // 继续向上寻找祖先节点
                }
                return cur;  // 找到后继节点后返回
            }
        }
        return null;  // 如果head为空，返回null
    }

    /**
     * insert 操作与search操作类似，都需要大致相同的循环流程
     * cur , p:遍历指针。 p始终是cur的父亲。
     * 时间复杂度：O(h)
     * @param val 值
     */
    public void insert(int val) {
        //保持p始终执行cur的双亲。
        Node p = null;
        Node cur = root;
        while (cur != null) {
            if (cur.val < val) {
                p = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return; //重复元素不允许插入。
            } else {
                p = cur;
                cur = cur.left;
            }
        }
        //p的位置就是新节点的父亲
        Node node = new Node(val);
        if (p == null) {
            //未进循环---本身未空树。让头指针指向新节点。
            root = node;
        }
        ///确认新节点是左还是右孩子。
        else if (p.val < val) {
            p.right = node;
        } else {
            // p.val > val
            p.left = node;
        }
    }

    /**
     * u是二叉搜索树或其子树的根节点
     * v 是顶替u位置的节点
     * 讨论了u是根节点的情形, v是null!即空树的场景。
     */
    private void transplant(Node u, Node v){
        if(u.p==null){
            //u.p==null 意味这u是整棵二叉搜索树的根节点。
            root = v;//修改根节点。
        }
        //u.p!=null 讨论u是其u.p的左孩子还是右孩子， 然后连接。
        else if(u == u.p.left){
            u.p.left = v;
        }
        else if(u == u.p.right){
            u.p.right = v;
        }
        if(v!=null){
            //单独处理v!=null
            v.p = u.p;
        }
        ///总之v相当与顶替u原先的地位，成为了u.p的孩子。
        ///但是仅处理了父子关系的连接， u还是连接着u.p,不过u.p已经不认u这个孩子了。
        ///其余指针的修改必须在函数外部处理了。
    }
    public void delete(int val) {
        Node cur = root;
        while (cur != null) {
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                // 找到要删除的节点
                break;
            }
        }
        if (cur == null) {
            // 没有找到值为 val 的节点
            return;
        }

        if (cur.left == null) {
            transplant(cur, cur.right);
        } else if (cur.right == null) {
            transplant(cur, cur.left);
        } else {
            Node successor = minimum(cur.right);
            if (successor.p != cur) {
                transplant(successor, successor.right);
                successor.right = cur.right;
                cur.right.p = successor;
            }
            transplant(cur, successor);
            successor.left = cur.left;
            cur.left.p = successor;
        }
    }

}